package 单周赛.history;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 */
public class 第337场单周赛 {

    public static void main(String[] args) {

    }

    public int[] evenOddBit(int n) {
        int[] ans = new int[2];
        for (int i = 0; i < 32; i++) {
            if (((n >> i) & 1) == 1) {
                if (i % 2 == 0) {
                    ans[0]++;
                } else {
                    ans[1]++;
                }
            }
        }
        return ans;
    }

    /**
     * 注意：骑士的行动是从下标 0 开始的，从左上角 出发，说明
     * 左上角必须是 0！！！
     */
    public boolean checkValidGrid(int[][] grid) {
        if (grid[0][0] != 0) {
            return false;
        }
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                map.put(grid[i][j], new int[]{i, j});
            }
        }

        for (int i = 1; i < grid.length * grid.length; i++) {
            int[] cur = map.get(i);
            int[] pre = map.get(i - 1);
            if (!(Math.abs(cur[0] - pre[0]) == 2 &&
                    Math.abs(cur[1] - pre[1]) == 1 ||
                    Math.abs(cur[1] - pre[1]) == 2 &&
                            Math.abs(cur[0] - pre[0]) == 1
            )) {
                return false;
            }
        }
        return true;
    }

    /**
     * 状态DP（超时！！！）
     */
    public static int beautifulSubsets(int[] nums, int k) {
        int cnt = 0;

        for (int i = 1; i < 2 << (nums.length - 1); i++) {
            Set<Integer> set = new HashSet<>();
            boolean flag = true;
            for (int j = 0; j < nums.length; j++) {
                if (((i >> j) & 1) == 1) {
                    if (set.contains(nums[j] - k) || set.contains(nums[j] + k)) {
                        flag = false;
                        break;
                    }
                    set.add(nums[j]);
                }
            }
            if (flag) {
                cnt++;
            }
        }

        return cnt;
    }

    /**
     * 统计 nums 中的的数对 value 取模的个数，负数取模的时候
     * 将其变成 >= 0 的数，枚举 [0-nums.len] 也进行取模运算
     * 和 nums 中的取模数进行抵消
     */
    public static int findSmallestInteger(int[] nums, int value) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int mod = (nums[i] % value + value) % value;
            map.put(mod, map.getOrDefault(mod, 0) + 1);
        }

        for (int i = 0; i < nums.length; i++) {
            if (map.getOrDefault(i % value, 0) > 0) {
                map.put(i % value, map.get(i % value) - 1);
            } else {
                return i;
            }
        }
        return nums.length;
    }

}
